'''
BM12 单链表的排序
'''


class ListNode:
    def __init__(self,val,next=None):
        self.val = val
        self.next = next

class Solution:

    def Merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1

        head = ListNode(0)
        cur = head

        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next

        if pHead1:
            cur.next = pHead1
        else:
            cur.next = pHead2

        return head.next

    def  sortInList(self , head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head

        left = head
        mid = head.next
        right = head.next.next

        while right != None and right.next != None:
            left = left.next
            mid = mid.next
            right = right.next.next

        left.next = None

        return self.Merge(self.sortInList(head),self.sortInList(mid))

def printList(node: ListNode):
    while node:
        print(node.val, end="->" if node.next else "\n")
        node = node.next

if __name__ == "__main__":
    phead1 = ListNode(3, ListNode(8, ListNode(7, ListNode(4, ListNode(1,ListNode(2))))))
    head = Solution().sortInList(phead1)
    printList(head)









